package org.opencv.samples.tutorial3;



public class Graph implements Cloneable
{
	private int[ ][ ] edges;
	private Object[ ] labels;
	public final static int INFINITY = 65536;

	/**
	 * Initialize a Graph with n vertices, no edges, and null labels.
	 * @param n
	 * the number of vertices for this Graph
	 */
	public Graph(int n)
	{
		edges = new int[n][n];  
		labels = new Object[n]; 
	}
	
	
	/**
	 *  Add a new edge to this Graph
	 * @param source
	 * the vertex number of the source of the new edge
	 * @param target
	 * the vertex number of the target of the new edge
	 * @param weight
	 * the weight value from the source vertex to the target vertex
	 */
	public void addEdge(int source, int target, int weight)   
	{
		// Undirected graph
		edges[source][target] = weight;
		edges[target][source] = weight;
	}
	
	
	/**
	 * Generate a copy of this Graph.
	 * @param - none
	 * @return
	 *   The return value is a copy of this Graph. Subsequent changes to the
	 *   copy will not affect the original, nor vice versa. Note that the return
	 *   value must be type cast to a Graph before it can be used.
	 */
	public Object clone( )
	{  
		// Clone a Graph object.
		Graph answer;

		try
		{
			answer = (Graph) super.clone( );
		}
		catch (CloneNotSupportedException e)
		{  
			// This would indicate an internal error in the Java runtime system
			// because super.clone always works for an Object.
			throw new InternalError(e.toString( ));
		}

		answer.edges = (int [ ][ ]) edges.clone( );
		answer.labels = (Object [ ]) labels.clone( );

		return answer;
	}
	
	
	/**
	 * Static method to print the labels of a graph with a depth-first search.
	 * @param g
	 * a not null Graph
	 * a vertex number from the Graph g
	 * @param start
	 */
	public static void depthFirstPrint(Graph g, int start)
	{
		boolean[ ] marked = new boolean [g.size( )];

		depthFirstRecurse(g, start, marked);

	}
	
	
	/**
	 * Recursive method to carry out the work of depthFirstPrint.
	 * @param g
	 * a not null Graph
	 * @param v
	 * a vertex number from the Graph g
	 * @param marked
	 *  an array to indicate which vertices of g have already been visited
	 */
	public static void depthFirstRecurse(Graph g, int v, boolean[ ] marked)
	{
		int[ ] connections = g.neighbors(v);
		int i;
		int nextNeighbor;

		marked[v] = true;
		System.out.println(g.getVertex(v));

		// Traverse all the neighbors, looking for unmarked vertices:
		for (i = 0; i < connections.length; i++)
		{
			nextNeighbor = connections[i];
			if (!marked[nextNeighbor])
				depthFirstRecurse(g, nextNeighbor, marked);
		} 
	}
	
	/**
	 * Accessor method to get the label of a vertex of this Graph.
	 * @param vertex
	 * a vertex number
	 * @return
	 * the label of the specified vertex in this Graph
	 */
	public Object getVertex(int vertex)
	{
		return labels[vertex];
	}
	
	
	/**
	 * Accessor method to determine whether this Graph contains a specified edge.
	 * @param source
	 * the vertex number of the source of the specified edge
	 * @param target
	 * the vertex number of the target of the specified edge
	 * @return
	 * The return value is true if this Graph has an edge from the
	 * specified source to the specified target.
	 * Otherwise the return value is false.
	 */
	public int getEdge(int source, int target)
	{
		return edges[source][target];
	}
	
	
	/**
	 *  Accessor method to obtain a list of neighbors of a specified vertex of this Graph
	 * @param vertex
	 * a vertex number
	 * @return
	 * The return value is an array that contains all the vertex numbers of
	 * vertices that are targets for edges with a source at the specified vertex.
	 */
	public int[ ] neighbors(int vertex)
	{
		int i;
		int count;
		int[ ] answer;

		// First count how many edges have the vertex as their source
		count = 0;
		for (i = 0; i < labels.length; i++)
		{
			if (edges[vertex][i] != INFINITY)
				count++;
		}

		// Allocate the array for the answer
		answer = new int[count];

		// Fill the array for the answer
		count = 0;
		for (i = 0; i < labels.length; i++)
		{
			if (edges[vertex][i] != INFINITY)
				answer[count++] = i;
		}

		return answer;
	}

	
	/**
	 * Remove an edge from this Graph.
	 * @param source
	 * the vertex number of the source of the removed edge
	 * @param target
	 * the vertex number of the target of the removed edge
	 */
	public void removeEdge(int source, int target)   
	{
		edges[source][target] = INFINITY;
	}
	
	
	/**
	 *  Modification method to change the label of a vertex of this Graph. 
	 * @param vertex
	 * a vertex number
	 * @param newLabel
	 * a new label (which may be null)
	 */
	public void setVertex(int vertex, Object newLabel)
	{
		int otherVertex;
		
		labels[vertex] = newLabel;
		
		for (otherVertex = 0; otherVertex < labels.length; ++otherVertex)
		{
			edges[otherVertex][vertex] = INFINITY;
			edges[vertex][otherVertex] = INFINITY;
		}
	}   

	
	/**
	 * Determine the number of vertices in this Graph.
	 * @return
	 *   the number of vertices in this Graph
	 **/ 
	public int size( )
	{
		return labels.length;
	}
	

	/**
	 * Print out this Graph.
	 */
	public void displayGraph( )
	{
		int weight;
		
		for (int i = 0; i < size( ); ++i)
		{
			for (int j = 0; j < size( ); ++j) 
			{
				weight = getEdge(i, j);
				if (weight == INFINITY)
					System.out.print("�� ");
				else
					System.out.print(weight + "  ");
			}
			System.out.println();
		}
	}
}
